#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

class Sort
{
public:
	void Print(vector<int>& nums)
	{
		for (auto& e : nums)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void  InsertSort(vector<int>& nums)
	{
		int size = nums.size();
		for (int i = 0; i < size - 1; i++)
		{
			for (int j = i + 1; j > 0 && nums[j - 1] > nums[j]; j--)
			{
				swap(nums[j], nums[j - 1]);
			}
		}
	}

	void ShellSort(vector<int>& nums, int n)
	{
		int size = nums.size();
		int gap = n;
		while (gap > 1)
		{
			gap = gap / 3 + 1;
			for (int i = 0; i < size - gap; i++)
			{
				for (int j = i; j >= 0 && nums[j] > nums[j + gap]; j -= gap)
				{
					swap(nums[j], nums[j + gap]);
				}
			}
		}

	}

	void SelectSort(vector<int>& nums)
	{
		int size = nums.size();
		int left = 0, right = size - 1;
		while (left < right)
		{
			int mini = left, maxi = left;
			for (int i = left + 1; i <= right; i++)
			{
				if (nums[i] < nums[mini])
					mini = i;
				if (nums[i] > nums[maxi])
					maxi = i;
			}
			swap(nums[left], nums[mini]);

			if (left == maxi)
				maxi = mini;
			swap(nums[right], nums[maxi]);

			left++;
			right--;
		}
	}

	void Ajustup(vector<int>& nums, int child)
	{
		int parent = (child - 1) / 2;
		while (parent >= 0)
		{
			if (nums[parent] < nums[child])
			{
				swap(nums[parent], nums[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}

	void Ajustdown(vector<int>& nums, int size, int parent)
	{
		int child = parent * 2 + 1;
		while (child < size)
		{
			if (child + 1 < size && nums[child] < nums[child + 1])
				child += 1;
			if (nums[parent] < nums[child])
			{
				swap(nums[parent], nums[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}
	void HeapSort(vector<int>& nums)
	{
		int size = nums.size();
		//priority_queue<int, vector<int>, less<int>> pq(nums.begin(), nums.end()); // 排升序建大堆
		//nums.clear();
		//while (!pq.empty())
		//{
		//	nums.push_back(pq.top());
		//	pq.pop();
		//}
		for (int i = (size - 1 - 1) / 2; i >= 0; i--) // 排升序建大堆
		{
			Ajustdown(nums, size, i);
		}
		int end = size - 1;
		while (end > 0)
		{
			swap(nums[0], nums[end]);
			Ajustdown(nums, end, 0);
			end--;
		}
	}

	void BubbleSort(vector<int>& nums)
	{
		int size = nums.size();
		bool flag = false;
		for (int i = 0; i < size - 1; i++)
		{
			for (int j = 1; j < size - i; j++)
			{
				if (nums[j - 1] > nums[j])
				{
					swap(nums[j - 1], nums[j]);
					flag = true;
				}
			}
			if (!flag) break;
		}
	}
};

int main()
{
	vector<int> v = { 9,1,3,7,4,6,2,5,8 };
	Sort sort;
	//sort.BubbleSort(v);
	//sort.InsertSort(v);
	//sort.ShellSort(v, 3);
	//sort.SelectSort(v);
	sort.HeapSort(v);
	sort.Print(v);
	return 0;
}